首先，我们得知道过原点与两点的抛物线解析式：
设该函数解析式为 且过 三点。
由函数过 得 。
P4778 Counting swaps
对于每个位置 i , 我们向 pi 连一条边。 结合题意可知，一个合法的排列，是一个由 n 个自环组成的图。
但现在会形成多个环，不妨记环的数量为 k ， 第 i 个环的大小为 si（包括自环）。
我们现在要做的，就是将这 k 个环拆成 n 个自环。
SP694 DISUBSTR - Distinct Substrings
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量，很容易列出转移式：
SP1811 LCS - Longest Common Substring
一道后缀自动机的板题。
我们从根结点开始匹配，如果有转移就将cnt++
不然就顺着后缀链接向上跳，直到找到有转移的点，用 Maxlen 继续匹配。(后缀链接一定是它的子串，也能被匹配)。
P2408 不同子串个数
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量，很容易列出转移式：
SP8222 NSUBSTR - Substrings
不难发现到f[i]就是长度为 i 子串的 ∣endpos∣ 的最大值。
根据一个性质后缀自动机的一个点的 endpos 被他的后继分为了很多部分，所以我们可以用parent树dp，处理出它的∣endpos∣。
接着是统计答案，显然我们可以用线段树覆盖。
P3195 [HNOI2008]玩具装箱TOY
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式：
设 sum 为 c 的前缀和，则有
0%
